package Test;

public class Test10 {
    //移动零
    public void moveZeroes(int[] nums) {
        int cur = 0;
        int des = -1;
        int n = nums.length;
        for(;cur<n;cur++){
            if(nums[cur] != 0){
                des++;
                int temp = nums[des];
                nums[des] = nums[cur];
                nums[cur] = temp;
            }
        }
    }
    //打家劫舍II(dp)
    public int rob(int[] nums) {
        int n = nums.length;
        //第一个房屋与最后一个房屋是挨着的
        //分成两类情况
        //选择第一个,不选择最后一个
        //选择最后一个 , 不选择第一个
        return Math.max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }
    int rob1(int[] nums,int l,int r){
        int n = nums.length;
        if(l > r) return 0;
        //选择第i个位置
        int[] f = new int[n];
        //不选第i个位置
        int[] g = new int[n];
        //注意初始化 , 传进来是怎样的参数
        f[l] = nums[l];
        for(int i = l + 1;i<=r;i++){
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        //这道题和按摩师那道题返回值不同
        return Math.max(g[r],f[r]);
    }
    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1 ;
        while(left < right){
            if(nums[left] + nums[right] > target){
                right--;
            }else if(nums[left] + nums[right] == target){
                return new int[]{nums[left],nums[right]};
            }else{
                left++;
            }
        }
        //下面两种都可以,为了照顾系统,没有什么用哈,返回数组就可以,它的值没要求,
        //因为只是为了照顾编译器
        // return new int[0];
        return new int[]{0};
    }
}
